Integrated circuits may be formed using photolithography processes with illumination sources having wavelengths more than twice a desired pitch of metal interconnect lines in the integrated circuits. Attaining desired tradeoffs between fabrication costs and fabrication yield may be difficult. For example, standard single photoresist patterns begin to blur at about the 45 nm feature size and 100 nm pitch (feature size plus space between features) when printing with 193 nm wavelength light.
Double patterning technology (DPT), illustrated in FIG. 1, may be used to print patterns with a pitch that is tighter than can be printed with a single exposure. In DPT technology approximately one half the geometries of the interconnect pattern 20 are placed on a first double patterning photo mask 22 and the remainder of the geometries are placed on a second double patterning photo mask 24. For example, a pattern with 100 nm pitch which prints blurred when all geometries are placed on a single photo mask may be decomposed into two DPT photo masks each with a 200 nm pitch which print without blurring. Geometries placed on the first DPT photo mask are described as having a first color and geometries placed on the second DPT photo mask are described as having a second color.
As shown in FIG. 2A in DPT the same color interconnect geometry design rule space 30 in the horizontal direction is larger than the different color interconnect geometry design rule space 32. Similarly, in FIG. 2B the same color interconnect geometry design rule space 34 in the vertical direction is larger than the different color interconnect geometry design rule space 36.
As shown in FIGS. 3A and 3B, unrestricted routing layout may result in color conflicts which violate DPT design rules. For example, in FIG. 3A vertical space 50 between same color preferred direction geometries 46 and 48 violates the vertical same color interconnect geometry design rule space 34. Similarly, in FIG. 3B, vertical space 56 between legs 54 and 52 violates the vertical same color design rule space 34. These are but two illustrative examples of conflicts that may occur with unrestricted layout. Many more may be found integrated circuit interconnect patterns. Resolving these conflicts to render a pattern DPT compatible may be computationally intensive and may also require significant relayout of the pattern. Both can significantly increase cost.
In order to draw the geometries on a single pattern that ensures the geometries are DPT compatible and may be decomposed into two DPT photo masks which each have a relaxed pitch, may be computationally intensive. The DPT layout splitting method is analogous to a two coloring problem for pattern splitting graph theory. The layout geometry and minimum space are similar to the vertex and edge of the graphs respectively. Two adjacent vertices connected with an edge should be assigned different colors. Only two “color types” can be assigned. Each pattern on the layer is assigned a first or second “color”. The patterns of the first color are formed on a first mask, and the patterns of the second color are formed on a second mask. A graph is 2-colorable only if after decomposition each mask contains no geometries of the same color that violate DPT design rules.